#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 0025.py
@time: 2021/9/26 14:38
@desc: https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/submissions/
'''
class Solution:
    def twoSum(self, nums: list, target: int) -> list:
        # 先找到上限
        n = len(nums)
        left, right = 0, n-1
        for i in range(n):
            if target<nums[i]:
                right = i -1
                break

        # target只有可能是左右两边相加
        i, j = left, right
        while i<j:
            cur = nums[i] + nums[j]
            if cur == target:
                return [nums[i], nums[j]]
            if cur > target:
                j -= 1
            if cur < target:
                i += 1

        return []

if __name__ == '__main__':
    nums = [16,16,18,24,30,32]
    res = Solution().twoSum(nums, 48)
    print(res)